The present invention relates generally to expert systems, and more particularly, to methods of compiling rule-based expert systems to provide multi-tasking code that achieves processing parallelism.
In recent years, rule-based expert systems have been proposed as a means for implementing complex decision-making processes for real-time embedded systems. While expert systems possess important advantages, there are currently significant limitations connected with their use in an embedded real-time operating environment. It is anticipated that many real-time paradigms will require inferencing throughputs exceeding those currently provided by typical expert system shells. The problem is expected to worsen as larger knowledge-based systems are developed to handle more sophisticated tasks. In addition, because expert systems are often prototyped using commercially available software tools, they are often incompatible with in-field hardware platforms, which tend to be more of a specialized, noncommercial, and high performance variety.
The interpretive nature of conventional expert systems make them slow and impractical to apply in applications requiring high computational throughputs. These expert systems, usually engineered on commercial development environments, are also difficult to embed and interface with system components written in conventional procedural languages, particularly those written in the Ada language. A few expert system shells purport to generate compiled representations of the rule base; however, their approach has been to migrate the entire inference mechanism down into procedural code, resulting in an extremely large, memory inefficient representation.
The areas of real-time performance, Ada interfaceability, and parallel processing for rule-based expert systems have not been generally addressed by commercial vendors of expert system shells. One instance of non-commercial reported research work does do compilation (see "Knowledge Base Compilation" by F. D. Highland and C. T. Iwaskiw in IJCAI-89). However, no mention is made of backward chaining capability as is employed in the present invention. Other research groups have investigated parallelization (see "Parallelism in Production Systems: The Sources and the Expected Speedup" by A. Gupta in Carnegie-Mellon Computer Science Dept. Tech Report CMU-CS-84-169, December 1984). However, their approach attempts to parallelize the entire inference engine (primarily the match phase) rather than use a custom approach as does the present invention. Thus, the amount of code produced by conventional approaches makes embedability impractical.
A paper entitled "Synthesis of Multitasking Ada Software for Real-Time Embedded Systems Using Knowledge Base Compilation", by Randall W. Lichota and Robert K. Chun, published in the Proceedings of Artificial Intelligence and Ada Conference, Nov. 14, 1990, examines three techniques that have been used to enhance expert system performance: rule compilation, parallel rule selection, and parallel rule execution. An approach is described in which a set of Ada tasks are synthesized from a knowledge base of rules. An analysis of the data and control dependencies is conducted to identify the parallelism implicit within a knowledge base. This information is then used to select distinct sets of rules that are used to derive individual procedures.
A paper entitled "Synthesis of Parallel Ada Code from a Knowledge Base of Rules", by Robert Chun et al., published in the Proceedings of the IEEE/ACM Symposium on Parallel and Distributed Processing, Dec. 1, 1991, generally describes the present invention as is described herein, but does not describe the full details of the compiler as is described herein.
Thus, it would be an advance in the art to have an expert system compilation tool that synergistically combines compilation, parallelization, compaction, real-time processing, backward-chained inferencing, and Ada interface capability.